import numpy as np

class DBSCAN:
    # 计算两个向量的欧氏距离
    def euclidean_dist(self, x1, x2):
        x = np.array(x1)
        y = np.array(x2)
        return np.linalg.norm(x - y)

    # 密度聚类
    def fit(self, data, neighbor_dist, minpts):
        """
        data: 数据集
        neighbor_dist: 邻域半径
        minpts: 构成核心对象的邻域最小样本数
        """
        # 初始化核心对象集合为空
        core_obj = set()
        # 初始化聚类个数为0
        cluster_num = 0
        # 初始化聚类列表clusters
        clusters = []
        # 初始化为访问样本集合P
        P = set(data)
        # 搜索核心对象
        for sample in data:
            # 如果样本sample的neighbor_dist邻域中样本数大于等于minpts
            if len([sample_i for sample_i in data if self.euclidean_dist(sample, sample_i) <= neighbor_dist]) >= minpts:
                core_obj.add(sample)
        # 开始聚类
        while len(core_obj):
            P_OLD = P  # 记录当前未访问的样本集合
            # 从核心对象集合中随机选取一个核心对象
            obj = list(core_obj)[np.random.randint(0, len(core_obj))]
            # 从未访问样本集合中删除核心对象obj
            P = P - set(obj)
            # 初始化队列Q
            Q = []
            Q.append(obj)
            while len(Q):
                q = Q[0]  # 取队首元素q
                # 获取q的neighbor_dist邻域
                N_q = [sample for sample in data if self.euclidean_dist(sample, q) <= neighbor_dist]
                # 如果领域中的样本数大于等于minpts
                if len(N_q) >= minpts:
                    delta = set(N_q) & P
                    Q += (list(delta))  # 将delta加入队列
                    P = P - delta  # 从未访问样本集合中删除delta
                Q.remove(q)  # 删除队首元素
            # 生成类簇C_k
            cluster_num = cluster_num + 1
            C_k = list(P_OLD - P)
            core_obj = core_obj - set(C_k)
            clusters.append(C_k)
        return clusters

if __name__ == '__main__':
    import matplotlib.pyplot as plt

    # 数据集：每三个是一组分别是西瓜的编号，密度，含糖量
    data = [(0.697, 0.460), (0.774, 0.376), (0.634, 0.264), (0.608, 0.318), (0.556, 0.215),
            (0.403, 0.237), (0.481, 0.149), (0.437, 0.211), (0.666, 0.091), (0.243, 0.267),
            (0.245, 0.057), (0.343, 0.099), (0.639, 0.161), (0.657, 0.198), (0.360, 0.370),
            (0.593, 0.042), (0.719, 0.103), (0.359, 0.188), (0.339, 0.241), (0.282, 0.257),
            (0.748, 0.232), (0.714, 0.346), (0.483, 0.312), (0.478, 0.437), (0.525, 0.369),
            (0.751, 0.489), (0.532, 0.472), (0.473, 0.376), (0.725, 0.445), (0.446, 0.459)]

    # 绘制聚类结果
    def draw(C):
        colValue = ['r', 'y', 'g', 'b', 'c', 'k', 'm']
        for i in range(len(C)):
            coo_X = []  # x坐标列表
            coo_Y = []  # y坐标列表
            for j in range(len(C[i])):
                coo_X.append(C[i][j][0])
                coo_Y.append(C[i][j][1])
            plt.scatter(coo_X, coo_Y, marker='x', color=colValue[i % len(colValue)], label=i)

        plt.legend(loc='upper right')
        plt.show()

    from DBSCAN import DBSCAN

    clustering_model = DBSCAN()
    clusters = clustering_model.fit(data, neighbor_dist=0.11, minpts=5)
    draw(clusters)